package 哈希;

public class vector<E> {
    private Object[] arr = null;
    public int length;
    private int capacity;

    public vector() {
        this.capacity = 2;
        length = 1;
        arr = new Object[capacity];
    }

    public vector(int capacity) {
        this.capacity = capacity;
        length = 1;
        arr = new Object[capacity];
    }

    public void reserve(int capacity){
        grow(capacity);
    }

    public void push_back(E elem){
        insert(elem,length-1);
    }

    public void insert(E elem,int pos) {
        if(length-1 == capacity)grow();
        arr[pos] = elem;
        length++;
    }

    private void grow(){
        grow((int) (this.capacity*1.5));
    }

    private void grow(int expansion){
        Object[] _new = new Object[expansion];
        int index = 0;
        for(Object i : arr){
            _new[index++] = i;
        }
        arr = _new;
        capacity = expansion;
    }

    public E at(int index){
        checkIndex(index);
        return (E) arr[index];
    }

    public int find(E elem){
        for(int i = 0;i<length-1;++i){
            if(arr[i].equals(elem))return i;
        }
        return -1;
    }

    public boolean remove(Object e){
        int index = find((E) e);
        if(index==-1)return false;
        remove(index);
        return true;
    }

    public E remove(int index){
        checkIndex(index);
        E temp = (E) arr[index];
        for(int i = index;i<=length-2;++i){
            arr[i] = arr[i+1];
        }
        arr[length-1] = null;
        --length;
        return temp;
    }

    public E set(int pos,E elem){
        checkIndex(pos);
        arr[pos] = elem;
        return elem;
    }

    private void checkIndex(int index){
        if(index < 0 || index > length)throw new ArrayIndexOutOfBoundsException("数组越界");
    }
}
